#include "fs/buf.h"
#include "dev/vio.h"
#include "lib/lock.h"
#include "lib/print.h"
#include "lib/str.h"

#define N_BLOCK_BUF 64
#define BLOCK_NUM_UNUSED 0xFFFFFFFF

// 将buf包装成双向循环链表的node
typedef struct buf_node {
    buf_t buf;
    struct buf_node* next;
    struct buf_node* prev;
} buf_node_t;

// buf cache
static buf_node_t buf_cache[N_BLOCK_BUF];
static buf_node_t head_buf; // ->next 已分配 ->prev 可分配
static spinlock_t lk_buf_cache; // 这个锁负责保护 链式结构 + buf_ref + block_num

// 链表操作
static void insert_head(buf_node_t* buf_node, bool head_next)
{
    // 离开
    if(buf_node->next && buf_node->prev) {
        buf_node->next->prev = buf_node->prev;
        buf_node->prev->next = buf_node->next;
    }

    // 插入
    if(head_next) { // 插入 head->next
        buf_node->prev = &head_buf;
        buf_node->next = head_buf.next;
        head_buf.next->prev = buf_node;
        head_buf.next = buf_node;        
    } else { // 插入 head->prev
        buf_node->next = &head_buf;
        buf_node->prev = head_buf.prev;
        head_buf.prev->next = buf_node;
        head_buf.prev = buf_node;
    }
}

// 初始化
void buf_init()
{
    spinlock_init(&lk_buf_cache, "buf_cache");
    head_buf.next = &head_buf;
    head_buf.prev = &head_buf;

    for (int i = 0; i < N_BLOCK_BUF; i++) {
        buf_node_t *bn = &buf_cache[i];
        bn->buf.block_num = BLOCK_NUM_UNUSED;
        bn->buf.buf_ref = 0;
        sleeplock_init(&bn->buf.slk, "buf_sleeplock");
        // 将 bn 插入到 head_buf.prev 的方向，即空闲列表
        insert_head(bn, false);
    }
}

static buf_node_t* buf_find(uint32 block_num)
{
    // 简单遍历
    buf_node_t *cur = head_buf.next;
    for (; cur != &head_buf; cur = cur->next) {
        if (cur->buf.block_num == block_num) {
            return cur;
        }
    }
    return NULL;
}

/*
    首先假设这个block_num对应的block在内存中有备份, 找到它并上锁返回
    如果找不到, 尝试申请一个无人使用的buf, 去磁盘读取对应block并上锁返回
    如果没有空闲buf, panic报错
    (建议合并xv6的bget())
*/
buf_t* buf_read(uint32 block_num)
{
    spinlock_acquire(&lk_buf_cache);

    // 尝试找到已有的buf
    buf_node_t *bn = buf_find(block_num);

    if (bn) {
        // 找到则buf_ref++
        bn->buf.buf_ref++;
        // 重新插入到head_buf.next(最近使用)
        insert_head(bn, true);
        spinlock_release(&lk_buf_cache);

        // 给buf上睡眠锁
        sleeplock_acquire(&bn->buf.slk);
        return &bn->buf;
    }

    // 没找到，需要从空闲列表找一个buf_ref=0的buf
    // 空闲buf在 head_buf.prev 方向
    buf_node_t *old = head_buf.prev;
    while (old->prev->buf.buf_ref==0&&old->prev!=&head_buf)
        old = old->prev;

    if (old->buf.buf_ref!=0) {
        // 没有空闲buf
        spinlock_release(&lk_buf_cache);
        panic("buf_read: no free buf");
    }
    // 现在 old 就是最老的空闲buf
    // 重置此buf
    old->buf.block_num = block_num;
    old->buf.buf_ref = 1;
    // 移动到 head_buf.next 一侧
    insert_head(old, true);

    spinlock_release(&lk_buf_cache);

    // 上锁，读磁盘数据

    sleeplock_acquire(&old->buf.slk);
    virtio_disk_rw(&old->buf, false);
    return &old->buf;
}

// 写函数 (强制磁盘和内存保持一致)
void buf_write(buf_t* buf)
{
    virtio_disk_rw(buf, true);
}

// buf 释放
void buf_release(buf_t* buf)
{
    sleeplock_release(&buf->slk);

    spinlock_acquire(&lk_buf_cache);

    // 从buf指针推回到buf_node_t指针
    buf_node_t *bn = (buf_node_t*)buf;

    buf->buf_ref--;
    if (buf->buf_ref == 0) {
        // 无人使用，移动到head_buf.prev一侧
        insert_head(bn, false);
    } else {
        // 仍有引用，将其放到head_buf.next表示最近使用过
        insert_head(bn, true);
    }

    spinlock_release(&lk_buf_cache);
}

// 输出buf_cache的情况
void buf_print()
{
    printf("\nbuf_cache:\n");
    buf_node_t* buf = head_buf.next;
    spinlock_acquire(&lk_buf_cache);
    while(buf != &head_buf)
    {
        buf_t* b = &buf->buf;
        printf("buf %d: ref = %d, block_num = %d\n", (int)(buf-buf_cache), b->buf_ref, b->block_num);
        for(int i = 0; i < 8; i++)
            printf("%d ",b->data[i]);
        printf("\n");
        buf = buf->next;
    }
    spinlock_release(&lk_buf_cache);
}